import Utils.SortUtils;

/**
 * 归并排序
 * @author xiaolu
 * @version 1.0
 * @date 2020/6/2 16:19
 */
public class Merge {

    // 声明归并所需要的辅助数组
    private static Comparable[] aux;

    // 一次性分配空间
    public static void sort(Comparable[] a){

        aux = new Comparable[a.length];
        sort(a, 0, a.length-1);
    }

    // 排序
    private static void sort(Comparable[] a, int lo, int hi){

        if (hi <= lo) return;
        int mid = lo + (hi - lo)/2;
        sort(a, lo, mid); // 将左半边排序
        sort(a,mid+1, hi); // 将右半边排序
        merge(a, lo, mid, hi);
    }

    public static void merge(Comparable[] a, int lo, int mid, int hi){

        int i = lo;
        int j = mid + 1;

        for (int k = lo; k <= hi; k++) {

            aux[k] = a[k];
        }

        // aux中分开排列好的数组依次比较，取小的值放入数组a中，当左边数组元素用完取右边数组的，右边用完取左边的
        for (int k = lo; k <= hi ; k++) {

            if (i > mid) a[k] = aux[j++]; // 左半边元素用尽(取右半边元素)
            else if (j > hi) a[k] = aux[i++]; // 右半边元素用尽(取左半边元素)
            else if (SortUtils.less(aux[j],aux[i])) a[k] = aux[j++]; // 右半边元素小于左半边当前元素(取右半边元素)
            else  a[k] = aux[i++]; // 右半边元素大于左半边当前元素(取左半边元素)

        }
    }

    public static void main(String[] args) {

        // Integer Input
        Integer[] arr = {4, 23, 6, 78, 1, 54, 231, 9, 12};
        Merge merge = new Merge();
        merge.sort(arr);

        // Output => 1 4 6 9 12 23 54 78 231
        SortUtils.show(arr);

        System.out.println("");

        // String Input
        String[] stringArray = {"c", "a", "e", "b", "d"};
        merge.sort(stringArray);
        //Output => a b c d e 
        SortUtils.show(stringArray);
    }

}
